
public class Leetcode121 {
    public static void main(String[] args) {
        System.out.println(maxProfit(new int[]{7, 1, 5, 3, 6, 4}));
    }

    public static int maxProfit(int[] prices) {
        Pair[] dp = new Pair[prices.length];
        dp[0] = new Pair(0, 0);
        dp[1] = new Pair(prices[0], prices[1]);
        return dp(prices.length - 1, dp, prices);
    }

    private static int dp(int n, Pair[] dp, int[] prices) {
        if (dp[n] != null) {
            return Math.abs(dp[n].k - dp[n].v);
        }

        int parent = dp(n - 1, dp, prices);
        if (prices[n] > Math.max(dp[n - 1].k, dp[n - 1].v)) {
            dp[n] = new Pair(Math.min(dp[n - 1].k, dp[n - 1].v), prices[n]);
            return Math.abs(dp[n].k - dp[n].v);
        } else {
            return parent;
        }

    }

    static class Pair {
        int k;
        int v;

        public Pair(int k, int v) {
            this.k = k;
            this.v = v;
        }
    }
}
